1. Field of the Invention
The present invention relates to a method for simulating contact between at least two volumetric objects delimited by triangular surfaces.
It finds a particularly useful application in the field of real-time to physical simulation for video games or surgical simulators. But it is of a broader scope since it can be applied to any simulation involving objects in contact with a non-trivial geometry.
2. Description of the Related Art
Simulation of mechanical objects can be broken down schematically into four main processes: collision detection, calculation of contact forces, calculation of internal forces, and time integration. Collision detection is often the most intensive processing operation and has been the subject of extensive detailed investigation for many years. This processing is important since the credibility of the simulation depends on it.
Precise geometric tests and in-depth calculations of intersection are necessary for determining forces of interaction between contact surfaces. The objects are generally broken down into contact primitives such as spheres or triangles. However, spherical primitives lead to rather unconvincing approximations of the contact surface and unfortunately give rise to substantial artefacts. Primitives based on triangles are more effective but require more geometric calculations than spheres. In any case, calculations of the repulsive forces are complex in application and discontinuous space functions may appear. For rigid objects, it is possible to carry out calculations beforehand in order to avoid these discontinuous functions, but this is difficult to envisage for deformable objects. Collision detection and the calculation of contact forces are therefore still extremely difficult tasks.
In the prior art there is the document of Teschner et al., “Collision detection for deformable objects.” Computer Graphics Forum 24, 1 (March 2005), 61-81, which describes collision detection and response techniques. This document describes techniques for creating bounding volume hierarchies to overcome the quadratic complexity inherent in collision detection. This document uses the distance field technique to obtain robust collision detection. In this technique, for any point in space, the “closest feature” is stored, being the surface element closest to this point, so as to permit deep intersections. In practice, this technique is only used for rigid objects as it requires previous calculations (preprocessing) of distance fields during initialization of the simulation. There are also still problems of discontinuity in the application of a 3D space to a surface, which can generate unstable responses.
In general, existing data processing systems, such as personal computers, include a graphics card which has the function of handling the processing and display of graphics components of ever increasing complexity. This graphics card in particular makes it possible to speed up 3D display. To do this, it includes a graphics processing unit (GPU), which is a processor optimized for 3D.
Recently, to exploit the computing power of GPUs and their capacity for efficient sampling of polygons, image-based methods were introduced. For given mesh geometries, these methods generate pairs of geometric primitives, which are then processed by the CPU for calculating the contact forces. As they do not use volumetric data structures, they can be applied effectively to rigid objects and deformable objects. The pairs of contacts can be composed of triangles or of points in volumes. After detection, additional calculations by the CPU are required for modelling the intersections and the contact forces.
The document by Heidelberger et al. “Real-time volumetric intersections of deforming objects”, in Proceedings of Vision, Modeling, Visualization (VMV), Munich, Germany, Nov. 19-21, 2003, which describes a layered depth image (LDI) algorithm, is known. This algorithm provides compact representation of several layers of the geometry of an intersection of objects from a given viewpoint. This algorithm makes it possible to construct geometric models of the intersection volume. According to this algorithm, the bounding boxes of the objects are calculated. Then, for each pair of potentially colliding objects, a visualization axis is selected and the entire surface of each object is rendered in a variety of textures (LDI). The surfaces contained in the intersection of the bounding boxes are visualized, said visualization being extended in the direction of visualization so as to include all the surface layers. Collision detection is then carried out taking into account consecutive pairs of texels (texture pixels), or triplets for self-collision, along the visualization axis. This quick and simple method avoids preprocessing operations. However, this document only deals with collision detection and says nothing about calculation of the contact forces.